Comparing Java and Ada Monitors queuing policies: a case study

Ada implementation of the global allocation solution

1. How to run the
Ada implementation of the global allocation solution

The main program is diner.adb
Once compiled (with GNAT for example), just run ./diner

-- dining philosophers paradigm.

-- Solution implementing global allocation of sticks
-- The chopsticks are allocated only when both are available

-- ADA solution using the eggshell semantic of Ada protected object
--an entry families


-- *************** reliable, no deadlock, not fair, starvation prone


2. A new solution for a well known paradigm, the dining philosophers

The dining philosophers, originally posed by Dijkstra [Dijkstra 7I], is a paradigm for concurrent resource allocation. Five philosophers spend their life alternately thinking and eating. To dine, each philosopher sits around a circular table at a fixed place. In front of each philosopher is a plate of food, and between each pair of philosophers is a chopstick. In order to eat, a philosopher needs two chopsticks, and they agree that each will use only the chopsticks immediately to the left and to the right of his place. The problem is to write a program simulating the philosopher’s behaviours and to devise a protocol that avoids two unfortunate conclusions. In the first one, all philosophers are hungry but none is able to acquire both chopsticks since each holds one chopstick and refuses to give it up. This is deadlock, a safety concern. In the second one, a hungry philosopher will always lack one of the two chopsticks which are alternately used by its neighbours. This is starvation, a liveness consideration.
This paradigm has two well known approaches for obtaining a solution. In the first one, the chopsticks are allocated one by one, and a reliable solution is obtained by adding one of the usual constraints for deadlock prevention: the chopsticks are allocated in fixed (e.g., increasing) order; a chopstick allocation is denied as soon as the requested allocation would lead to an unsafe state (seated dinner, with only 4 chairs). Ada implementation of this approach can be found [Burns 1995, Barkaoui 1997]. In the second one, the chopsticks are allocated globally only, which is a safe solution; when a fair solution is necessary, it is obtained by adding reservation constraints, care being taken that these constraints do not reintroduce deadlock. Ada implementation are given in [Brosgol 1996, Kaiser 1997]
Let us consider now another approach which does not seem to have been much experimented except in [Kaiser 1997]. The chopsticks are allocated as many as available and the allocation is completed as soon as the missing chopsticks are released. Let us observe the behaviour of this solution when implemented in Java and in Ada and from these experiments, let us determine the conditions of its correctness.



3. Ada global allocation

Ada program with the eggshell semantic.

The solution is in chop.adb

The solution is  instrumented for measuring a concurrency denials ratio.

4. The full paper : Comparing Java and Ada Monitors queuing policies: a case study